class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        n = len(price)
        bits, mask = 4, 0
        for i, need in enumerate(needs):
            mask |= need << i * bits
        
        @cache
        def dfs(special_i, need_cur):
            if need_cur == 0:
                return 0
            if special_i < 0:
                return sum(p * ((need_cur >> (i * bits)) & 0xF) for i, p in enumerate(price))
            
            if any(special[special_i][j] > ((need_cur >> (j * bits)) & 0xF)  for j in range(n)):
                return dfs(special_i-1, need_cur)
            
            nxt = need_cur
            for j in range(n):
                nxt -= special[special_i][j] << (j * bits)

            return min(
                    dfs(special_i-1, need_cur), 
                    dfs(special_i, nxt) + special[special_i][-1]
                )

        return dfs(len(special)-1, mask)